package com.kethink;

import java.util.Stack;

/**
 * @Author xuxiaojun
 * @date: 2019/3/1-23:20
 * @Description
 */
public class StackTest {

    public static void main(String[] args){
        String s = "5+4*6/2+3+(4*5)/5";//546*2/+3+45*5/+
//        String s = "2*(9+6/3-5)+4";//2963/+5-*4+

        System.out.println(convert(s));
    }

    /**
     * 等级很重要
     * 优先级最高的是"(",因为一定会进栈
     * 次之为"/*"
     * 再为"+-"
     * 优先级最低的是")",一定会连带其他的运算符出栈
     * 数字不进栈
     * @param c
     * @return
     */
    public static int level(char c){
        if("(".indexOf(c) > -1){
            return 3;
        }else if("*/".indexOf(c) > -1){
            return 2;
        }else if("+-".indexOf(c) > -1){
            return 1;
        }else if(")".indexOf(c) > -1) {
            return 0;
        }else {
            return -1;
        }
    }

    public static String convert(String ss){
        char[] chars = ss.toCharArray();
        //保存输出结果
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack();

        for (int i = 0; i < chars.length; i++){
            char c = chars[i];
            //数字不进栈
            if(level(c) == -1){
                sb.append(c);
            }else {
                //运算符
                if(stack.isEmpty()){
                    //栈为空，符号直接进栈
                    stack.push(c);
                }else {

                    if(level(c) > level(stack.peek())){
                        //进栈的运算符级别大于栈顶的级别
                        stack.push(c);
                    }else {

                        if(level(stack.peek()) == 3 ){
                            //栈顶是最高级别的是时候，进栈元素的级别是1-3
                            if(level(c) != 0){
                                //如果进栈的不是")"
                                stack.push(c);
                            }else {
                                //栈顶为"(",进栈元素")"
                                //不存在()里面没有运算符的,无意义
                            }
                        }else {
                            //栈顶不是最高级别

                            if(level(c) == 0){
                                //进栈是")",栈顶不是"(",先出栈,添加到返回值中
                                while (level(stack.peek()) != 3){
                                    sb.append(stack.pop());
                                }
                                //如果栈顶是"(",直接出栈
                                if(level(stack.peek()) == 3){
                                    stack.pop();
                                }
                            }else {
                                //进栈元素级别小于或等于栈顶元素级别
                                sb.append(stack.pop());
                                while (!stack.isEmpty()&&level(stack.peek()) >= level(c)&&level(stack.peek()) != 3){
                                    //循环出栈同级别的元素，出栈到返回值中
                                    sb.append(stack.pop());
                                }
                                stack.push(c);
                            }
                        }
                    }
                }
            }
        }

        //2+4  循环结束后，栈内还有运算符，出栈到返回值中
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}
